package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * @author tzp
 * @since 2020/9/16
 */
public class LC64 implements DynamicProblem {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        if (grid[0].length == 0) return 0;

        int[][] state = new int[grid.length][grid[0].length];

        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j == grid[0].length - 1) {
                    state[i][j] = grid[i][j];
                } else {
                    int min = Integer.MAX_VALUE;
                    if (i + 1 < grid.length) {
                        min = Math.min(min, state[i + 1][j]);
                    }
                    if (j + 1 < grid[0].length) {
                        min = Math.min(min, state[i][j + 1]);
                    }
                    state[i][j] = grid[i][j] + min;
                }
            }
        }
        return state[0][0];
    }

    public static void main(String[] args) {
        int[][] a = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        System.out.println(new LC64().minPathSum(a));
    }
}
